package Other;

import java.util.HashMap;
import java.util.Map;

public class leet_149 {
    public static void main(String[] args) {
        Solution_149 p = new Solution_149();
        System.out.println(18%6);

//        int[][] value = {{1,1}, {3,2}, {5,3}, {4,1}, {2,3}, {1,4}};


    }

}

class Solution_149{
    /**
     * (暴力法)
     * @param points  点的数组合集
     * @return 返回 k斜率 与d偏移量
     */
    public int twoPointLine(int[][] points){
        int allPoint = points.length;
        // 最后返回的最大值
        int res = 1;
        for(int i=0; i<allPoint; i++){
            // 第一个点
            int[] m1 = points[i];
            for(int j=i+1; j<allPoint; j++){
                // 第二个点
                int[] m2 = points[j];
                // 由2个点确定下来的斜率 得出在该斜率上的所有点
                // 这里为0是因为下面会遍历所有的点所以不需要设置起始值
                int count=0;
                // 拿出所有的点进行对比
                for(int k=0; k<allPoint; k++){
                    // 需要对比的第三个点
                    int[] m3 = points[k];
                    // 2个斜率相同时代表这2个点处在同一个线上
                    if(m1 == m3 || m2==m3){
                        count+=1;
                    }
                    else if((m1[1]-m2[1])*(m1[0]-m3[0]) == (m1[0]-m2[0])*(m1[1]-m3[1])){
                        count += 1;
                    }
                }
                // 比较2个值
                res = Math.max(res, count);
            }
        }
        return res;
    }


    /**
     * 使用hash映射 参考三叶大佬思路利用映射表来简化匹配问题
     * @param points
     * @return
     */
    public int twoPointLine2(int[][] points){
        // 总长度
        int pointLength = points.length;
        // 最大值
        int res = 1;
        for(int i=0; i<pointLength; i++){
            // 定义一个hash集合 统计斜率
            Map<String, Integer> map  = new HashMap<>();
            // 得出hash数组里面的最大值
            int max=0;
            // 第一个点
            int[] m1=points[i];
            for(int j=i+1; j<pointLength; j++){
                int[] m2=points[j];
                // 计算斜率, 但是斜率存在精度问题用str保留比较合适
                // 第二点 1/2  与 2/4 都是一个值但是用str保存起来就不同了所以得约分
                int tmp_1 = reductionFraction(m1[1]-m2[1], m1[0]-m2[0]);
                // 计算斜率
                String key = ((m1[1]-m2[1] )/tmp_1) + "_" + ((m1[0]-m2[0])/tmp_1);
                // 放入集合
                map.put(key, map.getOrDefault(key, 1) + 1);
                // 比较最大值
                max = Math.max(max, map.get(key));
            }
            // 上面max会赋值为0
            res = Math.max(res, max);
        }
        return res;
    }

    /**
     * 约分函数，取出2个相同的最小余数
     * @return 输出最大公约数
     */
    public int reductionFraction(int k, int m){
        int euclidNum = k%m;
        while(euclidNum!=0){
            k=m;
            m=euclidNum;
            euclidNum = k%m;
        }
        return m;
    }

}

